package main

// 215. 数组中的第K个最大元素
func main() {
	nums := []int{3, 5, 2, 56, 1}
	nums = []int{3, 2, 1, 5, 6, 4}
	k := 2
	kLargest := findKthLargest(nums, k)
	print(kLargest)

	//quickSort(nums)
	//for _, i := range nums {
	//	print(i, ",")
	//}
}

func findKthLargest(nums []int, k int) int {
	n := len(nums)
	return quickSelect2(nums, 0, n-1, n-k)
}

func quickSelect2(nums []int, l, r, k int) int {
	if l == r {
		return nums[k]
	}
	partition := nums[l]
	i := l - 1
	j := r + 1
	for i < j {
		for i++; nums[i] < partition; i++ {
		}
		for j--; nums[j] > partition; j-- {
		}
		if i < j {
			nums[i], nums[j] = nums[j], nums[i]
		}
	}
	if k <= j {
		return quickSelect2(nums, l, j, k)
	} else {
		return quickSelect2(nums, j+1, r, k)
	}
}

func findKthLargest2(nums []int, k int) int {
	n := len(nums)
	return quickSort1(nums, 0, n-1, n-k)
}

func quickSort1(nums []int, low, high, resIdx int) int {
	mid := partition1(nums, low, high)
	if mid == resIdx {
		return nums[resIdx]
	} else if mid > resIdx {
		return quickSort1(nums, low, mid-1, resIdx)
	} else {
		return quickSort1(nums, mid+1, high, resIdx)
	}
}

func partition1(nums []int, low, high int) (mid int) {
	pivot := nums[high]
	i := low - 1

	for j := low; j < high; j++ {
		if nums[j] < pivot {
			i++
			nums[j], nums[i] = nums[i], nums[j]
		}
	}
	nums[i+1], nums[high] = nums[high], nums[i+1]

	return i + 1
}

func quickSort(nums []int) {
	quickSortByIdx(nums, 0, len(nums)-1)
}

func quickSortByIdx(nums []int, low, high int) {
	if high > low {
		pivotIndex := partition1(nums, low, high)
		quickSortByIdx(nums, low, pivotIndex-1)
		quickSortByIdx(nums, pivotIndex+1, high)
	}
}

// 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
//
//请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
//
//你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
//
//示例 1:
//
//输入: [3,2,1,5,6,4], k = 2
//输出: 5
//示例 2:
//
//输入: [3,2,3,1,2,4,5,5,6], k = 4
//输出: 4
//
//提示：
//
//1 <= k <= nums.length <= 105
//-104 <= nums[i] <= 104
